package org.bean;

import org.example.bean.Production;
import org.example.bean.VT;

import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CopyOnWriteArraySet;

public class DFA {

    Set<Set<SLRProduction>> items;
    public Set<SLRProduction> item0;
    public List<String> itemList;

    Map<String,SLRProduction> slrMap;

    public List<String> toList(Set<SLRProduction> item){

        List<String> list = new ArrayList<>();
        if (item == null)
            return list;
        if (item.isEmpty())
            return list;
        for (SLRProduction slrProduction : item) {
            String s = slrProductionToString(slrProduction);
            list.add(s);
        }
        return list;
    }

    public String slrProductionToString(SLRProduction slrProduction){
        StringBuilder str=new StringBuilder();
        str.append(slrProduction.left).append("->");
        List<String> slrRight=new ArrayList<>(slrProduction.slrRight);
        slrRight.remove("·");
        for (String s : slrRight) {
            str.append(s);
        };
        return str.toString();
    }

    public ActionTable slrParseTable;

    public DFA(List<SLRProduction> productions){
        this.productions=productions;
        slrList=new ArrayList<>();
        for (SLRProduction production : productions) {
            slrList.add(production.toString());
        }
    }
    public List<SLRProduction> productions;

    public Set<String> symbols;

    public SLRProduction st;

    public String start;



    public void ptItems(){
        System.out.println(item0);
        System.out.println(symbols);
    }
    public List<String> slrList;
    public void init(){
        actionTableMap=new HashMap<>();
        symbols=new HashSet<>();
        gotoMap =new HashMap<>();
        for (SLRProduction production : productions) {
            symbols.add(production.left);
            symbols.addAll(production.slrRight);
        }
        Production production = productions.get(0);
        String left = production.left;
        List<String> right=new ArrayList<>();
        right.add("·");
        right.add(left);
        item0 = new HashSet<>();
        st=new SLRProduction(start, right);
        item0.add(st);
        slrList.add(0,st.toStringRemoveDot());
//        right=new ArrayList<>();
//        right.add(left);
//        st=new SLRProduction("start", right);
//        productions.add(0,st);
        actionTableList=new ArrayList<>();
        slrMap=new HashMap<>();
        for (SLRProduction slrProduction1 : productions) {
            String string = slrProduction1.left;
            slrMap.put(string, slrProduction1);
        }
        slrMap.put(st.left,st);
    }

    /*
    实现一个状态机使得求得所有项目集规范蔟
     */
    public Set<SLRProduction> closure(SLRProduction a){//这里的item其实拓广文法
        CopyOnWriteArraySet<SLRProduction> item = new CopyOnWriteArraySet<>();
        item.add(a);
        while (true) {
            boolean flag=false;
            for (SLRProduction slrProduction : item) {
                //查找list<string>集合中含有"."的元素的后一个元素A->a.Bb
                List<String> list=slrProduction.slrRight;
                int index=list.indexOf("·");
                if(index==list.size()-1){
                    //核心状态
                    continue;
                }
                String s = list.get(index + 1);
                if(s==null||s.isEmpty()){continue;};
                //找到list<string>集合中含有"."的元素的后一个元素
                //查找所有产生式中的B->C
                for (SLRProduction production : productions) {
                    if(production.left.equals(s)){

                        //找到B
                        //遍历B的所有的右部即B->c1,B->c2......
                        List<String> right=new ArrayList<>(production.slrRight);
                        right.add(0,"·");
                        SLRProduction slrProduction1 = new SLRProduction(s, right);
                            //加入item中
                            boolean isIN=false;
                            for (SLRProduction slrProduction2 : item) {
                                if(slrProduction2.left.equals(s)&&slrProduction2.slrRight.equals(right)){
                                    isIN=true;
                                    break;
                                }
                            }
                            if(!isIN){
                                SLRProduction slrProduction2 =new SLRProduction(slrProduction1.left,slrProduction1.slrRight);
                                if(!item.contains(slrProduction1))
                                    item.add(slrProduction1);
                                flag=true;
                            }
                    }
                }
            };
            if(flag)continue;
            else break;
        };
        return item;
    }

    public Map<String,Set<SLRProduction>> gotoMap;
    public Set<SLRProduction> goTo(Set<SLRProduction> item,String s){
        Set<SLRProduction> res=new HashSet<>();
        for (SLRProduction slrProduction : item) {
            int index = slrProduction.slrRight.indexOf(s);
            int area = slrProduction.slrRight.indexOf("·");
            if(area==-1||area>=index){
                //待优化，如果右部含有两个相同的非终结符
                continue;
            }
            if(slrProduction.slrRight.get(index-1).equals("·")){
                List<String>  right=new ArrayList<>(slrProduction.slrRight);
                //这里不能对item做修改，item来自原先的状态集之一
                right.remove(index-1);
                right.add(index,"·");
                SLRProduction slrProduction1 = new SLRProduction(slrProduction.left, right);
                Set<SLRProduction> I=closure(slrProduction1);
                res.addAll(I);
            };
        }
        return res;
    }

    public Set<SLRProduction> getAllItem(SLRProduction item){
        //神，竟然输出的状态集和书上顺序一样，明明是用set完成的，这顺序的一致性太吊了
        Set<SLRProduction> C=closure(item);
        CopyOnWriteArraySet<SLRProduction> res = new CopyOnWriteArraySet<>(closure(item));
        while(true){
            int num=res.size();
            for (SLRProduction slrProduction : res) {
                for (String symbol : symbols) {
                    Set<SLRProduction> I=new HashSet<>();
                    I.add(slrProduction);
                    I=goTo(I,symbol);
                    if(!ishave(res,I)&& !I.isEmpty()){
                        res.addAll(I);
                        boolean b = ishave(res, I);

                    }

                }
            };
            if (res.size() == num) {
                for (SLRProduction re : res) {
                    System.out.println(re);
                }
                return res;
            }
        }
    }

    public Map<String, Integer> itemMap;

    public List<ActionTable> actionTableList;

    public Map<String, ActionTable> actionTableMap;

    public List<Production> productionList;

    public void setProductionList(List<Production> productionList) {
        proMap=new HashMap<>();
        this.productionList = productionList;
        for (Production production : productionList) {
            proMap.put(production.left,production);
        }
    }

    public Map<String ,Production> proMap;

    public CopyOnWriteArrayList<CopyOnWriteArraySet<SLRProduction>> get_All_Item(SLRProduction item){
        itemMap=new HashMap<>();
        Set<SLRProduction> C=closure(item);
        CopyOnWriteArrayList<CopyOnWriteArraySet<SLRProduction>> items = new CopyOnWriteArrayList<>();
        items.add((CopyOnWriteArraySet<SLRProduction>) C);//item0
        for (SLRProduction slrProduction : C) {
            String str = slrProduction.toString();
            itemMap.put(str,0);
        }
            for(int i=0;i<items.size();i++){
                CopyOnWriteArraySet<SLRProduction> slrProductions=items.get(i);
//            for (CopyOnWriteArraySet<SLRProduction> slrProductions : items) {//为什么foreach遍历会失效，这个问题之后再探究
                int index=0;
                //生成每一个状态集
                for (String symbol : symbols) {
                    Set<SLRProduction> ans=new HashSet<>();

                //从状态集中遍历

                for (SLRProduction slrProduction : slrProductions) {
                    Set<SLRProduction> I=new HashSet<>();

                    //遍历每一个终结符
                    I.add(slrProduction);
                    I=goTo(I,symbol);
                    ans.addAll(I);
                    };
                    int flag=0;

                    for (SLRProduction production : ans) {
                        if(i==8&&symbol.equals("+"))
                            System.out.println("bug");
                        String str = production.toString();
                        if(!itemMap.containsKey(str)||flag==1){
                            flag=1;
                            itemMap.put(str,items.indexOf(slrProductions)+1);
                        }
                    };
                    CopyOnWriteArraySet<SLRProduction> res;
                    if(flag==1) {
                        res = new CopyOnWriteArraySet<>(ans);
                        System.out.println("状态 "+slrProductions);
                        System.out.println("遇到"+symbol+"转移到");

                        System.out.println(res);
                        items.add(res);//增加项目集
                        //初步求解action表
                        if(!VT.isVT(symbol))continue;

                        //非核心状态的action
                        ActionTable actionTable = new ActionTable();
                        actionTable.vt=symbol;
                        actionTable.item= items.indexOf(slrProductions);
                        int idx_1=items.indexOf(res);
                        actionTable.act="s"+idx_1;
                        if(actionTableMap.containsKey(actionTable.getIndex())){
                            System.out.println("分析表存在冲突1");
                            continue;
                        }
                        else {
                            actionTableMap.put(actionTable.getIndex(),actionTable);
                            actionTableList.add(actionTable);
                        }
                        if(!VT.isVT(symbol))continue;
                        //这里主要是求核心状态的action
                        for (SLRProduction slrProduction : slrProductions) {
                            int idx=slrProduction.slrRight.indexOf("·");
                            if(slrProduction.slrRight.contains("·")&&idx==slrProduction.slrRight.size()-1){
                                //是核心状态
                                String s = slrProduction.slrRight.get(idx - 1);
                                //要求follow集
                                    Production production = proMap.get(slrProduction.left);
                                    for (String string : production.follow) {
                                        ActionTable actionTable1 = new ActionTable();
                                        actionTable1.item=items.indexOf(slrProductions);
                                        actionTable1.vt=string;
                                        int idx_2 = itemList.indexOf(slrProductionToString(slrProduction));
                                        if(idx_2==0)
                                            actionTable1.act="acc";
                                        else actionTable1.act="r"+idx_2;
                                        if(actionTableMap.containsKey(actionTable1.getIndex())){
                                            System.out.println("分析表存在冲突");
                                            continue;
                                        }
                                        else {
                                            actionTableList.add(actionTable1);
                                            actionTableMap.put(actionTable.getIndex(),actionTable1);

                                        }
                                    }
                            };
                        }
                        String act="s"+items.indexOf(res);
                        new ActionTable(items.indexOf(slrProductions),symbol,act);
                    }
                    }
                };
        System.out.println("分析表");
        for (ActionTable actionTable : actionTableList) {
//            System.out.println(actionTable);
            System.out.println("action["+actionTable.item+","+actionTable.vt+"]="+actionTable.act);
        };
        int i=0;
        for (CopyOnWriteArraySet<SLRProduction> slrProductions : items) {
            System.out.println("状态 "+i+":"+slrProductions);
            i++;
        }
                return items;
    }

    /**
     * 求状态集，但是不求闭包，即只求核心项目
     * @param item
     * @return
     */
    public CopyOnWriteArrayList<CopyOnWriteArraySet<SLRProduction>>ITEMS;
    public CopyOnWriteArrayList<CopyOnWriteArraySet<SLRProduction>> getAllItemAndAction(SLRProduction item){
        itemMap=new HashMap<>();
        CopyOnWriteArrayList<CopyOnWriteArraySet<SLRProduction>> items = new CopyOnWriteArrayList<>();
        Set<SLRProduction> C = new HashSet<>();
        C.add(item);

        items.add(new CopyOnWriteArraySet<SLRProduction>(C));//item0
            String itemStr = item.toString();
            itemMap.put(itemStr,0);
        for(int i=0;i<items.size();i++) {
            CopyOnWriteArraySet<SLRProduction> slrProductions = items.get(i);
//            for (CopyOnWriteArraySet<SLRProduction> slrProductions : items) {//为什么foreach遍历会失效，这个问题之后再探究
            int index = 0;
            //生成每一个状态集
            for (String symbol : symbols) {
                boolean isNew=false;//定义跳转到或转移到的产生式是否是新的状态集

                Set<SLRProduction> ans = new HashSet<>();

                //从状态集中遍历

                boolean isReduse = false;//判断当前这个状态遇到这个文法符号是否会规约
                for (SLRProduction slrProduction : slrProductions) {//从当前这个状态的核心状态出发
//                    Set<SLRProduction> I=new HashSet<>();
                    //求核心状态的闭包得到非核心状态
                    Set<SLRProduction> I = closure(slrProduction);

                    int last = -1;//定义跳转到已存在的状态，主要用来检测是否所有的核心与非核心状态都跳转到同一个状态集，不是则分析表冲突
                    //遍历每一个终结符
                    boolean flag=false;//定义是否跳转到新的状态或者已存在的状态，而不是无法跳转，无法跳转的情况是规约项目
                    for (SLRProduction production : I) {
                        //状态之间的转换一定是从核心状态到另一个核心状态
                        List<String> list = production.slrRight;
                        int idx = list.indexOf("·");
                        if (list.contains(symbol) && list.indexOf(symbol) == idx + 1) {
                            //对于能够找到一个状态集的来说，他要么是移进要么是跳转

                            flag=true;
                            //新的状态集或跳转到另一个状态
                            List<String> slrRight = new ArrayList<>(list);
                            slrRight.remove(symbol);
                            slrRight.add(idx, symbol);
                            SLRProduction slrProduction1 = new SLRProduction(production.left, slrRight);
                            String str = slrProduction1.toString();
                            ActionTable actionTable = new ActionTable();
                            actionTable.item = items.indexOf(slrProductions);
                            actionTable.vt = symbol;
                            if (itemMap.containsKey(str)) {
                                if (last != -1 && last != itemMap.get(str)) {
                                    System.out.println("分析表存在冲突，此文法不是slr文法");
                                    throw new RuntimeException("该文法不是 slr文法");
                                }
                                else
                                    last = itemMap.get(str);
                            } else {
                                //生成新的状态
                                itemMap.put(str, items.size());
                                isNew=true;
                            };
                            ans.add(slrProduction1);
                            if (VT.isVT(symbol)) {
                                //这是移进
                                    actionTable.act = "s" + items.size();
                            }
                            else if(slrRight.indexOf("·")==slrRight.size()-1&&slrRight.indexOf(symbol)==slrRight.size()-2){
                                //这是跳转
                                //这里好像多余
                            }
                        }
                        else if(list.indexOf(symbol)==list.size()-2&&idx==list.size()-1){
                            //点在最右部
                            //无法跳转到其他状态
                            //说明是规约项目
                            Production production1 = proMap.get(production.left);
                            for (String s : production1.follow) {
                                ActionTable actionTable = new ActionTable();
                                actionTable.item= items.indexOf(slrProductions);

                                actionTable.vt=s;
                                actionTable.act="r"+slrList.indexOf(production.toStringRemoveDot());
                                if(actionTable.act.equals("r0"))//说明是接受状态
                                    actionTable.act="acc";
                                actionTableList.add(actionTable);
                                System.out.println("状态: " + slrProductions);
                                System.out.println("遇到 " +s + "用");
                                System.out.println("第" + slrList.indexOf(production.toStringRemoveDot()) + "条产生式规约\n");
                            }
                        }
                        ;
                    }
                    }

                //遍历完所有的核心状态后
                CopyOnWriteArraySet<SLRProduction> res = new CopyOnWriteArraySet<>(ans);

                if(!ans.isEmpty()) {
                    ActionTable actionTable = new ActionTable();
                    actionTable.item = items.indexOf(slrProductions);
                    actionTable.vt = symbol;
                    if(VT.isVT(symbol)) {
                        System.out.println("当前状态: " + slrProductions);
                        System.out.println("遇到" + symbol + "转移到");
                        System.out.println(ans);
                        System.out.println();
                        if(isNew)
                        actionTable.act = "s" + items.size();
                        else
                            actionTable.act = "s" + items.indexOf(res);
                        actionTableList.add(actionTable);
                    }
                    else{
                        if(isNew)
                        actionTable.act =""+items.size();
                        else
                            actionTable.act =""+items.indexOf(res);

                        actionTableList.add(actionTable);
                        System.out.println("当前状态: " + slrProductions);
                        System.out.println("遇到" + symbol + "跳转到");
                        System.out.println(ans);
                        System.out.println();
                    }
                };
                if (isNew&& !ans.isEmpty())
                    items.add((res));
                }
                ;
            }

//        System.out.println("分析表");
//        int t=-1;
//        for (ActionTable actionTable : actionTableList) {
//            if(t==-1)
//                t=actionTable.item;
//            if(actionTable.item!=t) {
//                System.out.println();
//                t=actionTable.item;
//            }
//            if(VT.isVT(actionTable.vt))
//                System.out.print("action["+actionTable.item+","+actionTable.vt+"]="+actionTable.act+" ");
//            else
//                System.out.print("goto["+actionTable.item+","+actionTable.vt+"]="+actionTable.act+" ");
//        };
//        System.out.println();
        int i=0;
        System.out.println("所有的状态集：");
        for (CopyOnWriteArraySet<SLRProduction> slrProductions : items) {
            System.out.println("状态 "+i+":"+slrProductions);
            i++;
        }
//        for (String s : slrList) {
//            System.out.println(s);
//        }
        return items;
    }
    public boolean ishave(Set<SLRProduction> s1, Set<SLRProduction> s2){
        for (SLRProduction slrProduction : s2) {
            boolean isIn=false;
            for (SLRProduction production : s1) {
                if(production.equals(slrProduction)){
                    isIn=true;
                    break;
                }
            };
            if(isIn)continue;
            else return false;
        };
        return true;
    };

    public void printParseTable(){
        for (ActionTable actionTable : actionTableList) {
            actionTableMap.put(actionTable.getIndex(),actionTable);
        }
        System.out.println("分析表");
        System.out.format("%-10s","");
        symbols.add("$");
        List<String> symbolList = new ArrayList<>(symbols);
        //对symbolList排序
        Collections.sort(symbolList);

        for (String symbol : symbolList) {
            System.out.format("%-10s",symbol);
        }
        System.out.println();
        int t=-1;
        for(int i=0;i< ITEMS.size();i++) {
            System.out.format("%-10s",i);
            for (String symbol : symbolList) {
                String index=i+","+symbol;
                ActionTable actionTable = actionTableMap.get(index);
                if(actionTable==null){
                    System.out.format("%-10s","");
                    continue;
                }
                if (VT.isVT(actionTable.vt))
//                    System.out.format("%-20s","action[" + actionTable.item + "," + actionTable.vt + "]=" + actionTable.act + " ");
                    System.out.format("%-10s",actionTable.act);
                else
//                    System.out.format("%-20s","goto[" + actionTable.item + "," + actionTable.vt + "]=" + actionTable.act + " ");
                    System.out.format("%-10s",actionTable.act);
            }
            System.out.println();
        }
    }
}
